Nauka
algorytmu
Aby zająć
się pisaniem programów, należy nabyć pewnych umiejętności, do których na pewno
trzeba zaliczyć:
Chęć nabycia
tych umiejętności zmusza do tego, aby starannie wykonywać swoją pracę. Widać z
tego, że pewne nawyki są przydatne nie tylko w informatyce, ale również w
naszym codziennym życiu. Jeżeli potrafimy rozwiązywać problemy za pomocą
komputera, wykorzystując języki programowania, to znaczy, że programujemy.
Zanim jednak poznamy konkretny język programowania i zaczniemy pisać
jakikolwiek program, należy nauczyć się posługiwania się algorytmami. Komputer
jest tylko maszyną, którą wykorzystujemy do własnych celów, bo komputer nie
myśli, lecz tylko wykonuje polecenia. Dlatego krok po kroku trzeba mu podać
czynności, jakie ma wykonać.
Co to jest algorytm? Wydaje się, że najbardziej
przystępną definicją będzie określenie algorytmu jako przepisu prowadzącego do
rozwiązania zadania, problemu. W przepisie tym podaje się opis czynności, które
trzeba wykonać, oraz dane, dla których algorytm będzie określony.
Co w takim przepisie
może się znaleźć?
Może być to np. przypisanie zmiennej określonej wartości (np. za x podstaw 3),
wyświetlenie w danym momencie wyniku obliczeń, pobranie danych z dostępnej bazy
danych. Mówimy, że podajemy instrukcje lub że będzie wykonana operacja. Dane
(stałe, zmienne, parametry), które są przetwarzane za pomocą instrukcji,
nazywamy obiektami. Wyróżnia się wiele obiektów - mogą to być liczby naturalne,
rzeczywiste, znaki, słowa. Rozwiązanie dowolnego problemu polega na wykonaniu w
określonej kolejności akcji na obiektach. Zbiór tych akcji nazywamy algorytmem.
Jakie
mogą być rodzaje algorytmów?
W jaki
sposób można przedstawić algorytm? Pierwszy i najprostszy to opis słowny, np.
po lekcjach pójdę do kiosku i kupię gazetę. Innymi przykładami mogą być:
podyktowanie przez telefon przepisu na zaparzenie herbaty czy wyjaśnianie
koledze, jak należy rozwiązać zadanie z matematyki. Przykładów takich zachowań,
kiedy widzimy, że występuje jakaś kolejność przewidywalnych działań, można
podawać bardzo wiele. To są przykłady opisów algorytmicznych.
Inny sposób to zapis algorytmu za pomocą schematu blokowego. Aby zapisać
algorytm za pomocą takiego schematu, trzeba poznać stosowane symbole i ich
znaczenie. Będziemy używać tzw. skrzynki - graficznego sposobu przedstawienia
czynności wykonywanych przez komputer. Skrzynki te łączone są za pomocą
strzałek. W ten sposób pokazujemy kolejność wykonywania akcji.
|
Skrzynki
START i STOP wskazują początek i koniec każdego algorytmu. Ze skrzynki START
wychodzi tylko jedna droga, do skrzynki STOP wchodzi, co najmniej jedno
połączenie. |
|
W
skrzynce instrukcyjnej umieszcza się po-lecenia do wykonania (instrukcje) - podstawienie,
obliczenie, wprowadzenie wartości. |
|
W
skrzynce warunkowej umieszcza się warunek, który decyduje o wyborze dalszej
drogi postępowania. Ze skrzynki wychodzą dwa połączenia: TAK (wybierane, gdy
warunek jest spełniony), NIE, (gdy warunek nie jest spełniony). |
|
W
skrzynce wejścia / wyjścia umieszcza się wprowadzane dane lub wyprowadzane
wyniki. Ze skrzynki wychodzi tylko jedno połączenie. |
Aby
dobrze zrozumieć algorytmy, należy samemu spróbować go ułożyć. Będzie
ciekawiej, gdy zaczniemy zadawać pytania i algorytm rozbudowywać.
Zacznijmy od najprostszego, książkowego algorytmu: chcę wyjść z domu i w
zależności od pogody wezmę parasol lub nie.
Opis słowny: przed wyjściem z domu sprawdzam, jaka jest pogoda; jeżeli pada,
zabieram parasol i wychodzę, jeśli nie pada, wychodzę. W tak prostym przypadku
spotykamy się z sytuacją, w której występuje sprawdzenie warunku. Słowem, które
będzie nas informować, że należy wprowadzić sprawdzenie warunku, jest słowo
"jeśli".
Opis za pomocą schematu
blokowego:
|
|
Drugi przykład
prostego algorytmu:
oblicz objętość prostopadłościanu o krawędziach długości: 3cm·5cm·8cm.
Słowny opis postępowania: aby obliczyć objętość, należy pomnożyć
przez siebie długości trzech krawędzi wychodzących z jednego wierzchołka;
długości muszą mieć jednakowe miano.
Z podanej treści zadania
wynika, że mamy dane długości potrzebnych krawędzi w jednakowych jednostkach.
Zadanie to nie sprawi nikomu żadnej trudności. Warto jednak pomyśleć, czy nie
można byłoby ułożyć takiego algorytmu, za pomocą, którego obliczymy objętość
każdego prostopadłościanu.
Opis słowny:
START - podaj długość pierwszej krawędzi; a:= - podaj długość drugiej krawędzi; b:= - podaj długość trzeciej krawędzi; c:= - wykonaj obliczenie V:= a*b*c - podaj wynik; V:= STOP |
W
przykładzie tym wykonywane czynności następują jedna po drugiej. Instrukcje
wykonywane są w takim porządku, w jakim zostały zapisane. Jest to przykład
algorytmu zapisanego w postaci sekwencji. |
Zad. domowe:
1. Zapisz powyższy algorytm za pomocą schematu blokowego.
2. Jakimi cechami musi charakteryzować się dobry algorytm?
Spotykamy się często z
takim sytuacjami, że musimy wykonywać pewną czynność aż do momentu, gdy
odniesiemy sukces, np. zrób dziesięć pompek; będziesz tak długo czytać wiersz,
aż nauczysz się go na pamięć; dopóki będziesz siedzieć cicho, nie zapytam cię.
Z tego wynika, że możemy spotkać się z trzema sytuacjami:, gdy musimy wykonać
czynność bądź zadaną ilość razy, bądź do momentu spełnienia warunku.
Wykonaj instrukcję r razy, np. przeczytaj wiersz trzy razy.
Opis słowny:
START
STOP |
W tym
przypadku mamy algorytm zapisany w postaci sekwencji. |
Schemat blokowy:
Można też wykonać to
inaczej:
Opis słowny:
START
STOP |
Występuje
tutaj sprawdzenie warunku. Gdy warunek nie jest spełniony, czynność trzeba
wy-konać jeszcze raz. |
Schemat blokowy:
Powtarzaj wykonanie
instrukcji aż do spełnienia warunku.
Przykładem takiego
algorytmu może być zmienione poprzednie zadanie: Czytaj wiersz tak długo, aż
nauczysz się go na pamięć.
Opis słowny:
Opis słowny:
STOP |
Wykonywanie
polecenia "przeczytaj wiersz" trwa tak długo, aż nauczysz się go na
pamięć. |
Schemat blokowy:
Dopóki warunek nie jest
spełniony, wykonuj podane instrukcje.
Są to polecenia typu: dopóki jest zimno, noś czapkę; dopóki nie poprawisz ocen,
nie pójdziesz grać w piłkę; dopóki nie zdasz egzaminu, nie będziesz jeździć
samochodem itd.
Dopóki jest czerwone
światło dla pieszych, stój i czekaj.
Opis słowny:
STOP |
Stój
tak długo, aż nie zapali się zielone światło! Warunkiem, który musi zostać
spełniony, jest zmiana światła. |
Schemat blokowy:
Przykładów tego rodzaju algorytmów jest bardzo wiele. W
zasadzie większość czynności można opisać algorytmem. Będą one mniej lub
bardzie rozbudowane, a zależy to od tego, do jakiego stopnia można przewidzieć
zachowanie lub wykonywanie czynności w różnych sytuacjach. Algorytmami
iteracyjnymi będą te, w których stosujemy pętlę, tzn. zapis, w którym nakażemy
wykonanie pewnej akcji jeszcze raz po sprawdzeniu warunku, który trzeba
spełnić.
Zad. domowe:
Twoim zadaniem będzie znalezienie przykładów zachowań algorytmicznych w życiu
codziennym, które można zapisać jako iteracje.
1. Zbuduj algorytm, za pomocą, którego można obliczyć
drugą i trzecią potęgę danej liczby.
BUDOWA ALGORYTMU: -
podaj liczbę a, STOP |
|
2. Zbuduj algorytm
służący do rozwiązania równania typu ax + b = 0
BUDOWA ALGORYTMU: -
podaj wartość współczynnika a, -
napisz rozwiązanie równania x:= STOP |
|
Problemy do samodzielnego rozwiązania:
BUDOWA ALGORYTMU:
STOP |
|
Przedstaw za pomocą algorytmu sposób na obliczanie gęstości ciała stałego.
Zapisz za pomocą algorytmu sposób na rozpoznawanie rodzaju ruchu ciała ze
względu na zmianę prędkości.
START
i.
jeśli
tak, pisz: ruch jednostajnie przyspieszony,
ii.
jeśli
nie, pisz: ruch jednostajnie opóźniony.
STOP
Zapisz powyższy algorytm za pomocą schematu blokowego.
Zadania do samodzielnego rozwiązania: